package com.cat.dataStructure;

import java.net.Inet4Address;
import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-swaps-to-sort-by-digit-sum/description/
 * @create 2025/9/23 20:53
 * @since JDK17
 */

public class Solution74 {
    int get(int n) {
        int ans = 0;
        while (n != 0) {
            ans += n % 10;
            n /= 10;
        }
        return ans;
    }


    public int minSwaps(int[] nums) {
        int n = nums.length, ans = 0;
        int[] h = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        List<int[]> sorted = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            h[i] = get(nums[i]);
            sorted.add(new int[]{nums[i], i});
        }
        sorted.sort((a, b) -> {
            int t1 = h[a[1]], t2 = h[b[1]];
            if (t1 != t2) {
                return t1 - t2;
            } else {
                return a[0] - b[0];
            }
        });
        for (int i = 0; i < n; i++) {
            map.put(sorted.get(i)[0], i);
        }
        for (int i = 0; i < n; i++) {
            while (nums[i] != sorted.get(i)[0]) {
                int t = map.get(nums[i]);
                int tt = nums[i];
                nums[i] = nums[t];
                nums[t] = tt;
                ans++;
            }
        }

        return ans;
    }
}
